An Internet Protocol (IP) network is a large distributed system in which individual routers automatically adjust their decisions on how to forward packets based on information they learn from their neighbors about the state of the network. This design permits rapid recovery in case of link or router failures by allowing affected routers to re-route packets around the failure as soon as they discover it. The Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) or the Intermediate System to Intermediate System (IS-IS) routing protocols are commonly used embodiments of this design.
However, the distributed mode of operation of such routing protocols makes it difficult for a network administrator to have a global view of the network at any given time, and in particular of how traffic is traversing the network. Because of this, many of the network management functions that are available for networks based on more traditional technologies, e.g., connection-oriented networks, such as frame relay or asynchronous transfer mode (ATM), are difficult if not impossible to replicate in IP networks.
For example, in a connection-oriented network, the state associated with each connection/user provides the network administrator with a ready handle for identifying which changes affect its path. In contrast, in IP networks, because packet forwarding decisions are local to each router, there is no state associated with the path taken by the packets belonging to a given user flow. As a result, it is difficult to precisely identify which network events are responsible for a change in the paths actually taken by those packets.
This difficulty is further compounded by the distributed routing decisions used by IP networks, which often result in network events influencing the choice of paths used by flows that are far remote from the network location where the event originated. For example, a link failure in one area may affect a path originating in a remote area by shifting its exit point out of that remote area from one router to another router, even though there were no events that directly impacted the path inside that remote area. Similarly, a new route advertised by a router in one area may shift the flow of traffic in another area on the other side of the network, simply because this new route becomes the more attractive exit point to reach a given set of destinations.
As a consequence, it is difficult in IP networks to easily identify what network event is responsible for a given path change and determine which paths may be affected by a given network event.
Accordingly, it is desirable to provide an improved method and system for monitoring and tracking the set of interfaces or links through which traffic from specific customer flows as it traverses an IP network.
The following is provided as additional background information about the Internet and Internet routing protocols to help the reader understand the context of the present invention:
The Internet is a global network that includes multiple interconnected smaller networks or Autonomous Systems (AS), also called routing domains. The delivery of packets across this Interconnection of Networks is carried out under the responsibility of the IP protocol suite. In particular, routing protocols are responsible for allowing routers to determine how best to forward packets toward their destination.
Internet routing protocols can be divided into intra-domain and inter-domain routing protocols, with inter-domain routing protocols communicating information between ASs, while intra-domain routing protocols are responsible for determining the forwarding of packets within each AS. The Routing Internet Protocol (RIP), Open Shortest Paths First (OSPF) and Intermediate System to Intermediate System (IS-IS) protocols are examples of intra-domain routing protocols, while the Border Gateway Protocol (BGP) is an example of an inter-domain routing protocol.
This general architecture and the associated suite of protocols are rapidly becoming the de facto technology on which modern communication networks are built. This dominance extends from simple local area networks to large-scale, international carrier networks, and is largely due to the robustness and efficiency of networks built using it. In particular, IP networks are often referred to as “connectionless”, as packet forwarding decisions are made individually by each router based solely on address information carried in the packet and on the router's local routing table. The routing table of a router is built independently of packet forwarding and is based on information it receives from its neighboring routers regarding the set of destinations they can reach. In other words, a router's routing table contains enough information to enable it to determine where to forward any packet it may receive so that the packet is ultimately delivered to its intended destination. This information is present without the need for the establishment of a connection ahead of time, hence the connectionless characterization of IP networks. The content of a router's routing table commonly consists of route entries together with a next hop that identifies the link or node towards which packets associated with the route should be forwarded. A route entry is itself usually made-up of a subnet number and a subnet mask that together identify the set of addresses for which the route is a match.
The route 16.2.25.0/24 is an example of a route with subnet number 16.2.25.0 and an associated subnet mask of 24 bits that have the following binary representations: 00010000.00000010.00011001.00000000 and 11111111.11111111.11111111.00000000, respectively, where the last 8 trailing 0's indicate “don't care” bits that are ignored when determining if a route matches a given address. A route is deemed a match for an address if, after eliminating the address bits that fall outside of the subnet mask, the remaining address bits match the corresponding subnet number bits. For example, the route 16.2.25.0/24 is a match for address 16.2.25.7, as the subnet mask of 24 of the route specifies that only the first 24 bits of the address need to be considered (the last 8 bits are ignored) when comparing address bits and subnet bits to determine if there is a match. Upon receipt of a packet, a router uses the destination address carried in the packet itself to perform a longest prefix match against entries contained in its routing table. The longest matching prefix identifies the route that has the largest number of matching bits, when matching is done as described above. For example, considering again the address 16.2.25.7 and the two route entries 16.2.25.0/24 and 16.2.0.0/16 that are both matches for this address, the longest prefix match is found to be the route 16.2.25.0/24 as it shares its first 24 bits with the address instead of only the first 16 bits as is the case for route 16.2.0.0/16.